/*
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

叶子节点 是指没有子节点的节点。
空间和时间都是 O(n2)
*/
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> resList = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        Queue<String> pathQueue = new LinkedList<>();
        pathQueue.offer(String.valueOf(root.val));

        while(!queue.isEmpty()){
            TreeNode curr = queue.poll();
            String path = pathQueue.poll();
            if(curr.left == null && curr.right == null){ //叶子结点的定义：不含任意 子节点
                resList.add(path);
            }
            if(curr.left != null){
                queue.offer(curr.left);
                // 需要重新 new 一个对象。避免 path 覆盖
                pathQueue.offer(new StringBuilder().append(path).append("->").append(curr.left.val).toString());
            }
            if(curr.right != null){
                queue.offer(curr.right);
                pathQueue.offer(new StringBuilder().append(path).append("->").append(curr.right.val).toString());
            }
        }
        return resList;

    }
}